#include<iostream>
#include<stack>

template<class T>
class ThreadBinaryTreeNode{
    friend class ThreadBinaryTreeNode<T>;
private:
    int leftTag, rightTag;
    ThreadBinaryTreeNode<T> *leftChild;
    ThreadBinaryTreeNode<T> *rightChild;
    T element;
public:
    ThreadBinaryTreeNode();
    ThreadBinaryTreeNode(const T& ele);
    ThreadBinaryTreeNode(const T& ele,ThreadBinaryTreeNode<T> *l,ThreadBinaryTreeNode<T> *r);
    ThreadBinaryTreeNode *getLeftChild() const;
    ThreadBinaryTreeNode *getRightChild() const;
    void setLeftChild(ThreadBinaryTreeNode<T> * l);
    void setRightChild(ThreadBinaryTreeNode<T> *r);
    T getValue() const;
    void setValue(const T& val);
};


template<class T>
class ThreadBinaryTree{
private:
    ThreadBinaryTreeNode<T> * root;
public:
    ThreadBinaryTree();
    ThreadBinaryTree(ThreadBinaryTreeNode<T> *r);
    ~ThreadBinaryTree();
    ThreadBinaryTreeNode<T> * getRoot();
    void InThread(ThteadBinaryTreeNode<T> *root,ThreadBinaryTreeNode<T>*pre);
    void InOrder(ThreadBinaryTreeNode<T>*root);
};


template<class T>
void ThreadBinaryTreeNode<T>::InThread(ThteadBinaryTreeNode<T> *root, ThreadBinaryTreeNode<T> *pre){
    ThreadBinaryTreeNode<T>* current;
    current = root;
    if(current!=NULL){
        InThread(current->leftChild,pre);
        if(current->leftChild== NULL){
            current->leftChild=pre;
            current->leftTag=1;
        }
        if((pre)&&(pre->rightChild == NULL)){
            pre->rightChild=root;
            pre->rightChild=1;
        }
        pre=current;
        InThread(current->rightChild,pre);
    }
}

template<class T>
void ThreadBinaryTree
